package code.class1;

import cn.hutool.core.util.ArrayUtil;

import java.util.*;

/**
 * https://leetcode.cn/problems/intersection-of-two-arrays-ii/
 * <p>
 * 两个数组的交集
 * 给定两个数组，编写一个函数来计算它们的交集。
 * 例子：
 * 输入: nums1 = [1,2,2,1], nums2 = [2,2]           输出: [2,2]
 * 输入: nums1 = [4,9,5],   nums2 = [9,4,9,8,4]     输出: [4,9]
 * <p>
 * 思路：
 * 用map计数，如果小于1，则没有交集
 */
public class Code01_Intersect {

    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 2, 2, 1};
        int[] nums2 = new int[]{2, 2};
        int[] intersect = intersect(nums1, nums2);
        System.out.println(ArrayUtil.toString(intersect));

        int[] arr1 = new int[]{1, 2, 3, 4, 4, 13}, arr2 = new int[]{1, 2, 3, 9, 10};
        int[] res = intersect2(arr1, arr2);
        System.out.println(ArrayUtil.toString(res));
    }

    public static int[] intersect(int[] arr1, int[] arr2) {
        Map<Integer, Integer> maps = new HashMap<>();
        int length = arr1.length;
        while (--length >= 0) {
            Integer val = maps.get(arr1[length]);
            maps.put(arr1[length], val == null ? 1 : ++val);
        }
        List<Integer> ans = new ArrayList<>();
        length = arr2.length;
        while (--length >= 0) {
            Integer val = maps.get(arr2[length]);
            if (val != null && val > 0) {
                ans.add(arr2[length]);
                maps.put(arr2[length], --val);
            }
        }
        int[] result = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            result[i] = ans.get(i);
        }
        return result;
    }

    public static int[] intersect2(int[] arr1, int[] arr2) {

        int p1 = 0, p2 = 0;
        List<Integer> ans = new ArrayList<>();
        while (p1 < arr1.length && p2 < arr2.length) {
            if (arr1[p1] < arr2[p2]) {
                p1++;
            } else if (arr1[p1] > arr2[p2]) {
                p2++;
            } else {
                ans.add(arr1[p1]);
                p1++;
                p2++;
            }
        }
        int[] result = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            result[i] = ans.get(i);
        }
        return result;
    }
}
